import java.util.Arrays;

/**
 * Created by zhourh on 2018/9/26.
 *
 * 给定两个二进制字符串，返回他们的和（用二进制表示）。

 输入为非空字符串且只包含数字 1 和 0。

 示例 1:

 输入: a = "11", b = "1"
 输出: "100"
 示例 2:

 输入: a = "1010", b = "1011"
 输出: "10101"

 */
public class AddBinary {

    public static void main(String[] args) {
        System.out.println(new AddBinary().addBinary("11", "1"));
        System.out.println(new AddBinary().addBinary("1010", "1011"));
    }

    public String addBinary(String a, String b) {
        if (a == null || a.isEmpty() || b == null || b.isEmpty()) {
            return null;
        }


        int maxLength = Math.max(a.length(), b.length());
        char[] result = new char[maxLength + 1];
        Arrays.fill(result, '0');
        boolean carry = false;
        for (int i = 0; i < maxLength; i++) {
            int A = a.length() > i ? a.charAt(a.length() - i - 1) - 48 : 0;
            int B = b.length() > i ? b.charAt(b.length() - i - 1) - 48 : 0;
            int C = A + B + (carry ? 1 : 0);
            if (C > 1) {
                carry = true;
                C = C % 2;
            } else {
                carry = false;
            }

            result[i] = (char) (C + 48);
        }

        if (carry) {
            result[maxLength] = '1';
        }

        StringBuilder ans = new StringBuilder(new String(result));
        ans.reverse();
        return ans.substring((ans.charAt(0) == '0' ? 1 : 0));
    }
}
